package Offer;

/**
 * 礼物的最大价值
 * @author 是阿秋啊
 * @date 2022/04/07 20:31
 **/
public class Num47 {
    public int maxValue(int[][] grid) {
        //由于dp[i][j] 只与dp[i−1][j] ,dp[i][j−1] ,grid[i][j] 有关系，因此可以将原矩阵.grid 用作dp 矩阵，即直接在grid 上修改即可。
        //应用此方法可省去dp 矩阵使用的额外空间，因此空间复杂度从
        //O(MN) 降至O(1)
        int m = grid.length;
        int n = grid[0].length ;
        // 加是基于第一列和第一行进行下推的
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.max(grid[i - 1][j],grid[i][j - 1]);
            }
        }
        return grid[m][n];
    }
}
